#!/usr/bin/env python
# _*_coding:utf-8_*_

"""
二叉树
@Time : 2022/1/29 9:40
@Author: RunAtWorld
@File: binary_tree.py
"""


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.val)


def traverse(root: TreeNode):
    """
    递归遍历
    """
    if not root:
        return
    print(root.val)
    traverse(root.left)
    traverse(root.right)


def print_tree(root: TreeNode):
    if not root:
        return
    que = [root]
    while que:
        level_len = len(que)
        for i in range(level_len):
            node = que.pop(0)
            if node:
                print(node.val, end=",")
            else:
                print("NULL", end=",")
            if node and not node.left and not node.right:
                # 表示该节点的左右为空
                continue
            if node:
                que.append(node.left)
                que.append(node.right)
        print()


def max_depth_backtrack(root: TreeNode):
    """
    遍历二叉树计算答案的思路: 回溯
    用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度。
    """
    # 记录最大深度
    depth_max_value = 0
    # 记录遍历到的节点的深度
    depth = 0

    def traverse(node: TreeNode):
        nonlocal depth, depth_max_value
        if not node:
            # 到达叶子节点，更新最大深度
            depth_max_value = max(depth_max_value, depth)
            return
        # 前序位置
        depth += 1
        traverse(node.left)
        traverse(node.right)
        # 后序位置
        depth -= 1

    traverse(root)
    return depth_max_value


def max_depth_dp(root: TreeNode):
    """
    分解问题计算答案的思路: 动态规划
    过子树的最大高度推导出原树的高度
    """
    if not root:
        return 0
    left_depth = max_depth_dp(root.left)
    right_depth = max_depth_dp(root.left)
    res = max(left_depth, right_depth) + 1
    return res


def pre_order(root: TreeNode):
    """
    前序遍历: 一遍遍历的思路
    """
    res = []

    def traverse(node: TreeNode):
        nonlocal res
        if not node:
            return
        # 前序位置
        res.append(node.val)
        traverse(node.left)
        traverse(node.right)

    traverse(root)
    return res


def pre_order_dp(root: TreeNode):
    """
    前序遍历: 分解为子问题的思路
    """
    if not root:
        return []
    res = []

    res.append(root.val)
    res.extend(pre_order_dp(root.left))
    res.extend(pre_order_dp(root.right))
    return res


def print_level(root: TreeNode):
    """
    把根节点看做第 1 层，如何打印出每一个节点所在的层数
    """

    def traverse(node: TreeNode, level=1):
        if not node:
            return
        # 前序位置
        print("%d 在第 %d 层" % (node.val, level))
        traverse(node.left, level + 1)
        traverse(node.right, level + 1)

    traverse(root, 1)


def print_sub_node_num(root: TreeNode):
    """
    打印出每个节点的左右子树各有多少节点:
    节点数 = 左子树节点数+右子树节点数
    """

    def traverse(node: TreeNode):
        if not node:
            return 0
        left_count = traverse(node.left)
        right_count = traverse(node.right)
        print("%d 节点左子树有 %d 个节点，右子树有 %d 个节点" % (node.val, left_count, right_count))
        return left_count + right_count + 1

    return traverse(root)


def diameterOfBinaryTree(root: TreeNode) -> int:
    """
    二叉树的最大直径
    """
    max_diameter = 0

    def max_depth(node: TreeNode):
        if not node:
            return 0
        nonlocal max_diameter
        left_depth = max_depth(node.left)
        right_depth = max_depth(node.right)
        # 后序位置顺便计算最大直径
        diameter = left_depth + right_depth
        max_diameter = max(diameter, max_diameter)
        # 注意这一行代码，这里一开始没有想到
        return max(left_depth, right_depth) + 1

    max_depth(root)
    return max_diameter


def level_traverse(root: TreeNode):
    """
    二叉树层序遍历
    """
    if not root:
        return
    que = [root]
    while que:
        level_len = len(que)
        for i in range(level_len):
            node = que.pop(0)
            # 访问节点
            print(node.val)
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)

if __name__ == '__main__':
    """
             1 
           /   \ 
          2      3 
        /  \   /  \ 
       4   5  6    7
      /     \ 
     8       9
    """
    n9 = TreeNode(9)
    n8 = TreeNode(8)
    n7 = TreeNode(7)
    n6 = TreeNode(6)
    n5 = TreeNode(5, right=n9)
    n4 = TreeNode(4, left=n8)
    n3 = TreeNode(3, n6, n7)
    n2 = TreeNode(2, n4, n5)
    n1 = TreeNode(1, n2, n3)
    # traverse(n1)
    print_tree(n1)
    print("max_depth:", max_depth_backtrack(n1))
    print("max_depth:", max_depth_dp(n1))
    print("pre_order:", pre_order(n1))
    print("pre_order_dp:", pre_order_dp(n1))
    print("打印层次:")
    print_level(n1)
    print("打印左右子树节点数:")
    print_sub_node_num(n1)
    print("层序遍历:")
    level_traverse(n1)
